package com.geticsen.leetcode;

import java.util.HashMap;
import java.util.Map;

//https://leetcode-cn.com/problems/target-sum/
public class Solution_494 {
    private static int res = 0;
    private static Map<String, Integer> cache = new HashMap<>();

    public int findTargetSumWays(int[] nums, int target) {
        cache.clear();
        return findTargetSumWays(nums, target, 0);
    }

    public static void findTargetSumWays1(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                res++;
            }
            return;
        }
        findTargetSumWays1(nums, target, index + 1, sum + nums[index]);
        findTargetSumWays1(nums, target, index + 1, sum - nums[index]);
    }

    public static int findTargetSumWays(int[] nums, int target, int index) {
        if (index == nums.length) {
            if (target == 0) {
                return 1;
            }
            return 0;
        }
        String key = index + "_" + target;
        if (cache.get(key) != null) {
            return cache.get(key);
        }
        int left = findTargetSumWays(nums, target + nums[index], index + 1);
        int right = findTargetSumWays(nums, target - nums[index], index + 1);
        cache.put(key, left + right);
        return left + right;
    }
}
